1. Field of the Invention
The present invention relates generally to a method and apparatus that enables the computation of the geolocation of a communication device, and particularly to the use of such a method and apparatus to compute the location of a mobile transmitter such as a mobile telephone (cell-phone) using either a handset-based or a network-based solution.
2. Description of the Prior Art
It is important to be able to geolocate a mobile telephone unit within a given service area both for security and for commercial reasons. As the number of wireless subscribers increase, an increasing number of emergency calls (911 calls) are expected to originate from mobile telephones. A study in the state of New Jersey indicated that about 43% of E-911 calls originated from mobile telephones (xe2x80x98State of New Jersey, Report on the New Jersey enhanced 911 system trial: The first 100 daysxe2x80x99, Jun. 16, 1997). Additionally, the Federal Communication Commission (FCC) has mandated that all mobile units should have a built-in location feature, such that mobile units are able to compute and transmit their location (to an accuracy of within 125 m) to a Public Safety Answering Point (PSAP) at least 67% of the time. This would facilitate emergency response to be dispatched to the site since the user may be incapacitated, or not be aware of their precise location. Besides emergency services, commercial applications involving location specific services such as advertising, location specific billing, fleet location monitoring, navigation, etc. are also envisioned in the near future.
The prior art for computing the location of a mobile telephone can be split into two broad categories; handset-based solutions and network-based solutions. Handset-based solutions are implemented such that the handset has the capability, using a Global Positioning System (GPS) or, alternatively, the time of arrival of signals (forward-link base station to mobile signals) from different base stations (at least 2 base stations are needed), the signal to noise ratio (SNR) of the signals, or a combination of GPS and time of arrival techniques, to ascertain its relative location with respect to the known, fixed locations of the Base Stations, and thereby its exact location, which it then can transmit to the network or to the PSAP.
There are significant drawbacks to using GPS because the use of a GPS involves additional hardware. Therefore, this handset-based discussion will focus on the use of a forward-link solution. In addition, GPS-alone solutions for mobile stations involve long acquisition times for the GPS signal and require a lot of power in the receiver of the mobile station. Server assisted GPS solutions overcome these limitations, but have poor reception deep inside buildings.
The basic principle of location computation, for a forward-link handset-based solution, is to receive signals from two or more base stations, and use the signal parameters (like SNR or times of arrival) to estimate the location of the handset from each of the base stations. Since the position of the base stations is known, knowledge of the relative position between the two or more fixed locations leads to an estimate of the location of the mobile station.
Network-based solutions involve two or more base stations simultaneously ascertaining the location of the mobile phone from which a location query has originated, relative to the base-stations, using the angle of arrival of the signals (a reverse-link mobile-to-base-station signal), the time(s) of arrival of the signals, or the signal-to-noise ratio of the signals actually received. The signal to noise ratios of these signals are compared to the pre-computed signal-to-noise ratios expected for different locations computed using drive test data. Thus, in a network based solution, two or more base stations receive the signal from the mobile station, i.e., on the reverse link, and those signal parameters (SNR, the time of arrival or the angle of arrival) are used by each base station to estimate the relative location of the mobile, and consequently, its actual location.
There are some deficiencies in each of the methods described above. Methods based on angle of arrival are susceptible to large errors when the base station and mobile station are close to one another; reflections of buildings can also cause huge changes in angles of arrival respect to the line of sight angle and induce errors. In addition, interference from xe2x80x98strongxe2x80x99 interfering sources may prevent adequate signal sources from being received and cause error in computation of location.
Given the importance of location determination, many approaches to computing the location of a mobile telephone exist in the patent literature. For example, U.S. Pat. No. 6,275,186, by Seung-Hyun Kong, teaches a solution where a dedicated searcher uses a combination of Signal-to-Interference ratios and times of arrival of the signal from a handset at multiple base stations to estimate its location. Both network- and handset-based solutions that depend on times of arrival and angle of arrival techniques share the problem that, in many environments, the three base stations needed to accurately locate the mobile transmitter are not xe2x80x98seenxe2x80x99 by the mobile transmitter because of the near-far problem. This happens because, on the forward link, the interference from a xe2x80x98strongxe2x80x99 base station contributes to the interference seen when the receiver is in the process of detecting and processing xe2x80x98weakerxe2x80x99 base stations.
In the case of network based solutions, interference from other mobile transmitters often prevents three base stations from being able to receive, detect and process the signal from a single mobile transmitter. This occurs because, in the reverse link between the mobile station and base station, especially for a base station that is not the serving base station for the mobile station in question, or for one that is not in handoff, the signals from the other mobiles sharing the bandwidth and being served by the base station cause interference in that base station""s ability to detect and process the signal from the mobile station that needs the location service.
U.S. Pat. No. 6,263,208, by Chang et al., proposes a solution that uses a pre-computed probability map of pilot strengths for a given cellular area, and uses the actual received pilot strengths to estimate the location. They do not specifically address the issue of how a solution may be obtained if an adequate number of pilot signals are not visible to the mobile unit. Thus, there is no teaching of how to solve the problems of angle of arrival, reflections, and strong signals.
U.S. Pat. No. 6,163,696, by Qi Bi and Wen-Yi Kuo, proposes a network based solution where fake handoff messages are used, i.e., the mobile station increases its power until the primary base station and two or more other surrounding base stations are able to receive its signal. This solution, however, will cause increased interference to the signals from the other served mobiles in the area for the base stations in question. Thus, this solution compounds the strong signal problem.
U.S. Pat. No. 5,812,086 to Bertiger et al. proposes a central transceiver and a re-transmitter in order to service users within buildings. Such a system would be very costly and would not permit a user to use a communication device for geolocation purposes in a building that was not fitted with such a system.
The use of power control on the reverse and forward links is designed to limit interference and to ensure that the cellular network is balanced and at its optimal capacity. But even with the use of power control, say, when a mobile phone is very close to a particular base station, such interference is unavoidable because the strength of the signal from that base station contributes to the interference when the mobile phone is in the process of receiving, detecting and processing the signal from base stations 2 and 3, which may be further away. Similarly, in the case of the reverse link, since the serving base station attempts to ensure that all received signals from its mobiles are received with similar power levels and consequently, a nearby mobile station that is requesting location service would have a low transmit power of insufficient strength for two, or even one additional base station to receive this signal accurately enough for location computation. Two approaches exist in the prior art to tackle the near-far problem.
First, U.S. Pat. No. 6,157,842, by Karlsson et al., teach us that the near-far problem can be solved through the cessation of transmission by the strong base station for short intervals, during which time the mobile station can detect and process signals from weaker base stations, taking advantage of the lack of interference from the xe2x80x98strongxe2x80x99 base station. This approach has the disadvantage of potential disruption of communications for other served mobiles of the xe2x80x98strongxe2x80x99 base station. While this approach addresses the strong signal problem, it does not provide a viable solution. In addition, it does not address the angle of arrival or the reflection issues.
Second, U.S. Pat. No. 5,736,964, by Ghosh et al., teaches a solution that relies on the presence of backup emergency pilot generators that are used if a plurality of base stations is not visible. This is an expensive solution since it calls for the installation of equipment that only serves the purpose of location computation. While this approach addresses the strong signal problem, it may not provide a viable solution. In addition, it does not address the angle of arrival or the reflection issues.
Clearly, being able to receive multiple signal sources at a single transceiver, or, multiple transceivers being able to receive a single signal for a network-based solution, is critical to location determination. However, under real conditions, this is often not possible because of interference. The source of interference in spread spectrum systems is generated from the fact that all signal sources share the same bandwidth, all the time, and are simultaneously transmitting.
In spread spectrum systems, each transmitter may be assigned a unique code and in many instances each transmission from a transmitter is assigned a unique code. These codes may be used to spread the signal so that the resulting signal occupies some specified range of frequencies in the electromagnetic spectrum or the codes may be superimposed on another signal that might also be a coded signal. Assigning a unique code to each transmitter allows the receiver to distinguish between different transmitters.
If a single transmitter has to broadcast different message to different receivers, such as a base-station in a wireless communication system broadcasting to different mobiles, one may use codes to distinguish between the messages for each mobile unit. In this scenario, each bit for a particular user is encoded using the code assigned to that user. By coding in this manner, the receiver, by knowing its own code, may decipher the message intended for it from the composite signal transmitted by the transmitter. In some instances, such as in a coded radar system, each pulse is assigned a unique code so that the receiver is able to distinguish between the different pulses based on the codes.
The key idea in all of these coded systems is that the receiver knows the codes of the message intended for it and, by correctly applying the codes, the receiver may extract the message intended for it. However, such receivers are more complex than receivers that distinguish between messages by time and/or frequency alone. The complexity arises because the signal received by the receiver is a linear combination of all the coded signals present in the spectrum of interest at any given time. The receiver has to be able to extract the message intended of it from this linear combination of coded signals.
The following section presents the problem of interference in linear algebraic terms followed by a discussion of the current, generic (baseline) receivers.
Let H be a vector containing the spread signal from source no. 1 and let xcex81 be the amplitude of the signal from this source. Let si be the spread signals for the remaining sources and let xcfx86i be the corresponding amplitudes. Suppose the receiver is interested in source number 1, the signals from the other sources may be considered to be interference. Then, the received signal is:
y=Hxcex81+s2xcfx862+s3xcfx863+ . . . +spxcfx86p+nxe2x80x83xe2x80x83(1) 
where n is the additive noise term, and p is the number of sources in the Code-Division Multiple Access (CDMA) system. Let the length of the vector y be N, where N is the number of points in the integration window. This number N is selected as part of the design process as part of the trade-off between processing gain and complexity. A window of N points of y will be referred to as a segment.
In a wireless communication system, the columns of the matrix H represent the various coded signals and the elements of the vector xcex8 are the powers of the coded signals. For example, in the base-station to mobile link of a CDMA system, the coded signals might be the various channels (pilot, paging, synchronization and traffic) and all their various multi-path copies from different base-stations. In the mobile- to base-station link, the columns of the matrix H might be the coded signals from the mobiles and their various multi-path copies.
Equation (1) may now be written in the following matrix form:                                                         y              =                              xe2x80x83                            ⁢                                                H                  ⁢                                      xe2x80x83                                    ⁢                  θ                                +                                  S                  ⁢                                      xe2x80x83                                    ⁢                  φ                                +                n                                                                                        =                              xe2x80x83                            ⁢                                                                    [                                          H                      ⁢                                              xe2x80x83                                            ⁢                      S                                        ]                                    ⁡                                      [                                                                                            θ                                                                                                                      φ                                                                                      ]                                                  +                n                                                                        (        2        )            
where
H: spread signal matrix of the source that the receiver is demodulating
S=[s2 . . . sp]: spread signal matrix of all the other sources, i.e., the interference
xcfx86=[xcfx862 . . . xcfx86p]: interference amplitude vector
Receivers that are currently in use correlate the measurement, y, with a replica of H to determine if H is present in the measurement. If H is detected, then the receiver knows the bit-stream transmitted by source number 1. Mathematically, this correlation operation is:
correlation function=(HTH)xe2x88x921HTyxe2x80x83xe2x80x83(3) 
where T is the transpose operation.
Substituting for y from equation (2) illustrates the source of the power control requirement:                                                                                                               (                                                                  H                        T                                            ⁢                      H                                        )                                                        -                    1                                                  ⁢                                  H                  T                                ⁢                y                            =                                                                    (                                                                  H                        T                                            ⁢                      H                                        )                                                        -                    1                                                  ⁢                                                      H                    T                                    ⁡                                      (                                                                  H                        ⁢                                                  xe2x80x83                                                ⁢                        θ                                            +                                              S                        ⁢                                                  xe2x80x83                                                ⁢                        φ                                            +                      n                                        )                                                                                                                          =                                                                                          (                                                                        H                          T                                                ⁢                        H                                            )                                                              -                      1                                                        ⁢                                      H                    T                                    ⁢                  H                  ⁢                                      xe2x80x83                                    ⁢                  θ                                +                                                                            (                                                                        H                          T                                                ⁢                        H                                            )                                                              -                      1                                                        ⁢                                      H                    T                                    ⁢                  S                  ⁢                                      xe2x80x83                                    ⁢                  φ                                +                                                                            (                                                                        H                          T                                                ⁢                        H                                            )                                                              -                      1                                                        ⁢                                      H                    T                                    ⁢                  n                                                                                                        =                              θ                +                                                                            (                                                                        H                          T                                                ⁢                        H                                            )                                                              -                      1                                                        ⁢                                      H                    T                                    ⁢                  S                  ⁢                                      xe2x80x83                                    ⁢                  φ                                +                                                                            (                                                                        H                          T                                                ⁢                        H                                            )                                                              -                      1                                                        ⁢                                      H                    T                                    ⁢                  n                                                                                        (        4        )            
It is the middle term, (HTH)xe2x88x921HTSxcfx86, in the above equation that results in the near-far problem. If the codes are orthogonal, then this term reduces to zero, which implies that the receiver has to detect xcex8 in the presence of noise (which is (HTH)xe2x88x921HTn) only. It is easy to see that, as the amplitude of the other sources increases, the term (HTH)xe2x88x921HTSxcfx86 contributes a significant amount to the correlation function, which makes the detection of xcex8 more difficult.
The normalized correlation function, (HTH)xe2x88x921HT, defined above, is in fact the matched filter and is based on an orthogonal projection of y onto the space spanned by H. When H and S are not orthogonal to each other, there is leakage of the components of S into the orthogonal projection of y onto H. This leakage is geometrically illustrated in FIG. 1.
While the near-far problem has various implications on capacity of communication networks in terms of the interference limiting the number of users, say, on the forward and reverse link of a CDMA system, it is our intent here to focus on the solution to the near-far problem that hinders the ability to precisely identify the location of a mobile transmitter.
Thus, there is a need for an apparatus and method that facilitates either a mobile station being able to receive, detect and process signals from multiple base stations or multiple base stations being able to receive, detect and process signals from a single mobile station, to facilitate the ability of the mobile station or the network to precisely calculate the location of the mobile station in question. Preferably, this solution would function under conditions when interference from a xe2x80x98strongxe2x80x99 base station prevents the mobile station from xe2x80x98seeingxe2x80x99 weaker base stations, and on the reverse link, when interference from many xe2x80x98strongxe2x80x99 mobiles prevents the base stations from xe2x80x98seeingxe2x80x99 the mobile station that requires location service.
It is therefore an object of the present invention to provide a method and apparatus for geolocaton which will allow gelolocation of weak signals.
It is a further object to provide a method and apparatus for geolocation that utilizes the orthogonal projection of a signal to cancel interference associated with that signal.
According to a first broad aspect of the present invention, there is provided a method for determining geolocation of a mobile transmitter, the method comprising the steps of: generating a location request; detecting a first source signal (y1); generating an orthogonal projection of the first source signal; canceling interference from the first source signal by utilizing the orthogonal projection; detecting at least one more source signal (y2 . . . yn); and utilizing the source signals to determine the location of the mobile.
According to a second broad aspect of the invention, there is provided an apparatus for determining geolocation of a mobile, the apparatus comprising: means for generating a location request; means for detecting a first source signal (y1); means for generating an orthogonal projection of the first source signal; means for canceling interference from the first source signal by utilizing the orthogonal projection; means for detecting at least one more source signal (y2 . . . yn); and means for utilizing the source signals to determine the location of the mobile transmitter.
According to a third broad aspect of the invention, there is provided a method for improving the signal to noise ratio of a source signal by adjusting the correlation length of the source signal, the method comprising the steps of: (A) assigning a first pre determined correlation length to a variable N; (B) increasing the correlation length N by an amount Y; (C) determining the signal to noise ratio of the source signal; (D) comparing the signal to noise ratio to a predetermined threshold to determine if the signal to noise ratio is equal to or above the threshold, if below the threshold, then initiating step E otherwise, initiating step F; (E) comparing the correlation length to a predetermined maximum correlation length and if below the maximum correlation length, returning to step B, otherwise going to step F; and (F) transmitting the source signal for further processing.
According to a fourth broad aspect of the invention, there is provided an apparatus for improving the signal to noise ratio of a source signal by adjusting the correlation length of the source signal, the apparatus comprising: a means for assigning first pre determined correlation length to a variable N; a means for increasing the correlation length N by an amount Y; a means determining the signal to noise ratio of the source signal; and a means for comparing the signal to noise ratio to a predetermined threshold to determine if the signal to noise ratio is equal to or above the threshold, if below the threshold, then initiating a comparing means, otherwise, initiating a transmitting means; wherein the comparing means compares the correlation length to a predetermined maximum correlation length and if below the maximum correlation length, returning to the means for increasing the correlation length, otherwise initiating the transmitting means; and the transmitting means for transmitting the source signal for further processing.
According to a fifth broad aspect of the invention, there is provided a method for determining geolocation of a mobile transmitter, the method comprising the steps of: (A) generating a location request; (B) detecting a first source signal (y1); (C) assigning a first pre determined correlation length to a variable N; (D) increasing the correlation length N by an amount Y; (E) determining the signal to noise ratio of the first source signal (y1); (F) comparing the signal to noise ratio to a predetermined threshold to determine if the signal to noise ratio is equal to or above the threshold, if below the threshold, then initiating step G otherwise, initiating step H; (G) comparing the correlation length to a predetermined maximum correlation length and if below the maximum correlation length, returning to step D, otherwise going to step H; (H) generating an orthogonal projection of the first source signal; (I) canceling interference from the first source signal by utilizing the orthogonal projection; (J) detecting at least one more source signal (y2 . . . yn); and (K) utilizing the source signals to determine the location of the mobile.
According to a sixth broad aspect of the invention, there is provided a method for determining geolocation of a mobile transmitter, the method comprising the steps of: (A) generating a location request; (B) detecting a first source signal (y1) at a first base station; (C) generating an orthogonal projection of the first source signal; (D) canceling interference from the first source signal by utilizing the orthogonal projection; (E) detecting the first signal source (y1) at least one more base station; and (F) utilizing timing information of the source signal to determine the location of the mobile.
According to a sixth broad aspect of the invention, there is provided an apparatus for determining geolocation of a mobile transmitter, the apparatus comprising: means for generating a location request; means for detecting a first source signal (y1) at a first base station; means for generating an orthogonal projection of the first source signal; means for canceling interference from the first source signal by utilizing the orthogonal projection; means for detecting the first signal source (y1) at least one more base station; and means for utilizing timing information of the source signal to determine the location of the mobile.
Other objects and features of the present invention will be apparent from the following detailed description of the preferred embodiment.